
\section{Introduction}
\label{sec:intro}
Today's mobile devices have become an important
source of one's personal information. In daily life, people use
their mobile phones to send/receive text messages/emails, take
photos and videos, organize their activities and manage their
address book. Mobile is an ubiquitous platform for
relationship-building, learning, entertainment, commerce, and social
networking. Also, mobile search plays a major role in meeting the
growing users' demand for information from anywhere and anytime.
Allowed by the rapid growth of flash memory, the data generated from
the above activities can be stored on the mobile phone for a long
period of time. With the huge amount of mobile data, a lot of new
applications can be developed such as user preference learning,
context aware advertising and location based social network
services.
\begin{figure}
  % Requires \usepackage{graphicx}
  \includegraphics[width=3.3 in ]{Figures/mobile.eps}\\
  \caption{An example of the mobile community.}\label{figure:mobile}
\end{figure}

The data mentioned above are generated by different applications,
e.g. camera, calendar and message applications, but they can
associate with each other given some attributes they have in common.
For example, we can find relevancy between a photo and an event in
the calendar if the photo is taken in the same period when the event
is happening. Figure \ref{figure:mobile} demonstrates the data
objects related to a "graduation ceremony" event on July 5th.
Besides the photo-calendar relationship we just mentioned, the
calendar entry can be associated to text messages that talk about
the event. In addition, the tags of a photo may refer to a contact
in the address book. In this example, 'Wenchang' is a name of a
contact in the address book and is also a tag in the photos taken on
that day. In some use cases, the mobile user needs to navigate from
one object (e.g. a calendar event) to another object (e.g. a photo)
through some common attributes. In this example, the user might be
willing to call 'Wenchang' when he/she sees the photo.  Other use
cases may require efficient query mechanisms to discover the
relationship between two and more objects, such as finding the
common interests from two contacts from the content of text message
received from them.

There are primarily two research trends for searching the mobile data. The first one follows the thread of clouding computing. Basically, all data are uploaded to a server (or cloud), then index and search computing are performed by the server, finally the search results are sent back to the mobile devices. There are two limitations of the mobile cloud computing: data transfer cost and privacy. Frequent data upload/download will result in unnecessary power consumption and high communication cost as well; while the privacy issue restricts many important information to be uploaded onto the server. This leads to the other research trend to perform the search directly on mobiles referred to as mobile search.

%Please re-draw Figure 1 by deleting the temperature. Instead, we can
%add an address book. please also make their connection more
%explicitly. For example, showing an example of a photo's meta data
%like time and tags and use a line to connect between the related
%value.

The first issue for mobile search is how to manage the heterogeneous
data (e.g., emails, photos, and events) on the mobiles. These use
cases require a shared data storage where heterogeneous data from
different applications are stored and connected. Currently, there is
lack of a platform to support storing and accessing the mobile data.
Instead, different mobile applications store and manage their data
separately by themselves. Thus they can be shared only through the
application APIs. Obviously, it may result in redundancy and
inconsistency. Given shared data storage, the data can be used
across application boundaries. In addition, we need a common data
representation format which is simple but expressive enough for
utilization by as many types of applications as possible. Ontology
is used to define basic terms and relations comprising a vocabulary,
as well as rules for combining the terms and relations. In
particular, RDF can be a basic description framework for formally
representing and sharing the ontology for mobile data. Given the
graph structure of RDF, we can link different types of information
using their common attributes. For example, in Figure
\ref{figure:relation}, the circle nodes represent different users
while the triangle nodes represent different photos taken by these
users. And the edge in red means the friendship while the edge in
green means the ownership. For each photo, we have several tags
describing the main idea of it.

\begin{figure}
  % Requires \usepackage{graphicx}
  \includegraphics[width=3.3 in ]{Figures/photo-relation.eps}\\
  \caption{An example of the mobile community.}\label{figure:relation}
\end{figure}


Despite of many RDF storage and query solutions have been developed,
few of them consider the mobile environment. In particular, how to
achieve acceptable time and space performance is the key to the
success of using RDF as a mobile storage solution.
On the other hand, some related studies have been conducted to develop various
novel data mining applications on mobile devices. For example,
MobileMiner \cite{wang:mobileminer} is platform for mining user profiles from the users' continuous moving and calling records.
Works \cite{zheng:learning,zheng:location} try to discover the transportation mode and classical travel sequences from the GPS information collected from mobile devices.
\hide{
 Several researchers have done some
research about spatial mining given the pervasiveness of GPS-enabled
device. For instance, in \cite{zheng:learning,zheng:location}, the
authors make use of the raw data collected from the GPS devices, and
mine some valuable and interesting information like the
transportation mode and classical travel sequences in a region. }A
fundamental question is still open: how to efficiently access the
heterogeneous mobile data? The problem is non-trivial and poses
several unique challenges:
\begin{itemize}
  \item {\em Query interface.} The query processes in different applications on mobiles may be very different. Thus how to design a unified query interface is a challenging problem.

  \item {\em Index compression.} Due to the memory limitation, it is infeasible to directly adapt the conventional indexing technique to the mobile devices. It is necessary to design a method to compress the graph index while preserving the accessing efficiency.

  \item {\em Probabilistic graph query.} The heterogeneous data are linked with each other. However, it is unclear how to quantify the ``strength'' of each link.
\end{itemize}

\hide{
Of all these applications, mobile querying is also a basic
and necessary task. In summary, fast and efficient mobile query is
important for both users and business purposes.

\begin{itemize}
  \item {\em For users.} Mobile users need to access and manipulate information and services specific to certain situation.
  A mobile query system can help users reflect on their past events and deeply understand their life patterns as well.
  \item {\em For Business purposes.} There are tremendous market opportunities on mobile applications, especially for advertising business.
  Mobile query plays a significant role in facilitating and manipulating the mobile context through the device.
\end{itemize}
}

\hide{
However, the query process in different applications on mobiles are
independent and a unified toolkit for mobile query is needed to
facilitate and improve the performance of all the applications and
services on the mobiles. For the best of our knowledge, there is no
unified toolkit for mobile query released online and this is our
focus in this work. Another challenge lies in the textual
information on mobile devices, such as the contents of messages and
emails. Traditional keyword-based query can just return all the
objects containing the given keywords. But it has several
disadvantages for it: 1) Sometimes the user

Traditional keyword-based query can return all the objects
containing the keyword. However, it has several disadvantages for a
keyword-based query on mobile: 1)Since there are many different
types of data on mobile, sometimes we need to differentiate them,
for example, for a query "sports meeting", we want to get all the
SMSs talking about the sports meeting rather than some photos taken
that day. 2)The heterogenous data on mobiles are interdependent and
have many inner relationships so that results only based on keyword
might ignore many implicit but valuable information based on the
structural relationships. For example, /(some examples are needed
here/).Consequently, in this work, we want to make use of both the
textual description of different objects, like the keyword-based
query goes, and the structural relationship between them, which can
be viewed as graph query.
}


\hide{
Another challenge is related to the text content on mobile devices, such as the contents of text messages and emails.
Unlike the traditional keyword-based query that just returns all the objects containing the given keywords, our system
needs to support the association between the contents and other data objects. For example, given a text message that
mentions a place such as the summer palace, the system needs to rapidly find the photos taking in the surrounding area
using their geographic tags. Consequently, in this work, we want to make use of both
the textual description of different objects, like the keyword-based query, and the structural relationship between them, which can be
viewed as graph query.



%Another challenge is related to the text content on mobile
%devices, such as the contents of text messages and emails.
%Traditional keyword-based query can return all the objects containing the keyword.
%However, to support our use cases, the content has to ben
%linked and indexed
%it has several disadvantages on mobile settings:
%1)Since there are many different types of data on mobile, sometimes we need to differentiate them, for example, for a query "sports meeting",
%we want to get all the SMSs talking about the sports meeting rather than some photos taken that day. 2)The heterogenous data on mobiles are
%interdependent and have many inner relationships so that results only based on keyword might ignore many implicit but valuable information
%based on the structural relationships. For example, /(some examples are needed here/).Consequently, in this work, we want to make use of both
%the textual description of different objects, like the keyword-based query goes, and the structural relationship between them, which can be
%viewed as graph query.

It is worth noting that device-centric mobile data storage and query
is still needed given the rapid development of cloud computing which
encourages people to store their data in the cloud(server). The main
reason is that mobile devices cannot afford to continuously send
huge amount of data through internet, no matter GPRS, 3G or WIFI is
used. According to our experience, the battery of a mobile phone can
only last for a few hours if the phone constantly sends/receives
data. In addition, the mobile network is usually slow and unstable
so data loss and delay can easily happen. Another issue is the
 privacy concern since people normally regard their data on a mobile
 phone as highly personal and are not willing to send it to a server.
}

In addition, mobile search should consider the following restrictions: limited computing power, less memory capacity,
\hide{
restricted network access capability, lower bandwidth, higher price
of data transfer, varying network transfer rates, varying
availability of network }
and limited battery capacity.
To address the above challenges, we formulate and tackle the problem of querying for the mobile context data, and make the following contributions.
\hide{
As discussed
previously, in this work, we focus on the device-centric mobile
query toolkit, which can solve the problem related to the network
access capability, lack of infrastructure and possible delays in
network communication.


In this paper, we try to make the following contributions:
}First, we formalize the mobile search problem and design four types of general query on the mobiles. To address the limitation of computing power and memory capacity, we use a compression method to significantly improve the query efficiency on both memory cost and time cost.
Second, we propose a novel query of probabilistic subgraph, which uses an affinity propagation to quantify the probability of each link from the mobile data. Based on the discovered link probability, we develop a probabilistic subgraph query interface.
Third, we develop a unified toolkit, Mquery, and apply it to two real-world applications in NOKIA, photo-sharing system and mobile calling/moving monitoring system. Experimental results in the two systems demonstrate the effectiveness and the efficiency of the Mquery toolkit.

\hide{
present a device-centric client computing query system,
  which needs no external support of a remote server and is free from the communication
  delay or loss.

In terms of query, we use both the textual description
   and structural link information to get both the explicit and implicit results.

Due to the limitation of computation power and capacity of mobiles, we
  implement an efficient and fast query methods with low cost of memory and time.

We develop a unified toolkit, Mquery, for further applications.
  And we will use it in NOKIA photo sharing system(more needs to be added here to
  show the high applicability of Mquery).
}

The rest of the paper is organized as follows: \secref{sec:problem}
defines the preliminary concepts and briefly formulates the problem
of graph query for mobile context; \secref{sec:approach} explains
the proposed approach. Our performance study is reported in
\secref{sec:exp}. Related work is discussed in \secref{sec:related}
 Finally,
\secref{sec:conclude} concludes our study.

%\secref{sec:exp}
%illustrates several applications of TAP on real datasets.
